package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:35
 * @Des 回文链表
 */
public class LeetCode_234 {
    public static void main(String[] args) {
        // 使用额外空间存储
        m1();

        // O(1)空间
        m2();
    }


    /**
     * 回文链表
     * 快慢指针
     * 1.慢指针找到中点，按顺序存储前半段值
     * 2.遍历后半段，比对
     */
    public static void m1() {
        LinkNode head = new LinkNode(3);
        int[] vals = {4,4,6,4,4,3};
        head = LinkNode.formLink(head,vals);

        if(head == null || head.next == null) {
            System.out.println(false);
            return;
        }

        if(head.next.next == null) {
            String res = head.val == head.next.val ? "是回文链表" : "不是回文链表";
            System.out.println(res);
            return;
        }

        LinkNode slow = head;
        LinkNode fast = head.next.next;
        List<Integer> preHalfVals = new ArrayList<>();
        preHalfVals.add(slow.val);

        while (fast != null) {

            if(fast.next == null) {
                slow = slow.next;
                break;
            }

            slow = slow.next;
            preHalfVals.add(slow.val);
            fast = fast.next.next;
        }

        int index = preHalfVals.size();
        slow = slow.next;
        //slow往后半段走
        while (slow != null && !(index < 0)) {
            if(preHalfVals.get(index-1) != slow.val) {
                System.out.println("不是回文链表");
                return;
            }
            slow = slow.next;
            index--;
        }
        System.out.println("是回文链表");
    }

    public static void m2() {
        LinkNode head = new LinkNode(1);
        int[] vals = {2,2,1};
        head = LinkNode.formLink(head,vals);
        System.out.println(charge(head));
    }

    public static boolean charge(LinkNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        if(head.next.next == null) {
            if(head.val == head.next.val) {
                return true;
            } else{
                return false;
            }
        }

        /**
         1. 快慢指针先找到中间；
         2. 再用慢指针逆置后半部链表
         3. 记录后半部指针头结点
         4. 比较两部分链表是否相同
         **/
        LinkNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if(fast != null && fast.next == null) {
            slow = slow.next;
        }

        LinkNode pre = slow;
        LinkNode back = pre == null ? null : pre.next;
        pre.next = null;
        // 逆置后半部
        while(back != null) {
            LinkNode lastTemp = back.next;
            back.next = pre;
            pre = back;
            back = lastTemp;
        }

        // 遍历pre
        while(pre != null) {
            if(pre.val != head.val) {
                return false;
            }
            pre = pre.next;
            head = head.next;
        }

        return true;
    }
}
